package backtrack;

import java.lang.String;

import java.util.LinkedList;
import java.util.List;
import java.lang.*;

public class NQueens {

    //结果集
    static List<List<String>> result = new LinkedList<>();

    /**
     *
     * @param n 表示行数
     * @return 返回棋盘布局的集合。
     */
    public List<List<String>> solveNQueens(int n) {


        //初始化棋盘布局
        char[][] layout = new char[n][n];
        init(layout,n);
        //从第0行开始
        backTrack(layout,0);

        return result;
    }

    /**
     * 对应做回溯题的框架，函数传入两个参数
     * 保存的路径以及选择列表
     * @param layout
     * @param row
     */
    public void backTrack(char [][] layout,int row) {
        //结束条件
        //达到结束条件，将当前棋盘加入到结果集合中
        if (row == layout.length){
            List<String> res = new LinkedList<>();
            for (int i = 0; i < layout.length; i++) {
//                List<String> res = new LinkedList<>();
//
//                String string = String.valueOf(layout[i]);
//                res.add(string);
//
//                result.add(res);
                String string =  String.valueOf(layout[i]);
                res.add(string);
            }
            result.add(res);
            return ;
        }



        for (int i = 0; i < layout[row].length; i++) {
            //判断此处可否放皇后
            if (!valid(layout,row,i)) continue;
            //做出选择
            layout[row][i] = 'Q';
            //进入下一次选择
            backTrack(layout,row + 1);
            //回退
            layout[row][i] = '.';
        }


    }

    /**
     * 判断此位置能否放皇后,返回true表示有效，返回false表示无效
     * @param row
     * @param col
     * @return
     */
    public boolean valid(char[][] layout,int row,int col) {
        boolean flag = true;
        //行
        for (int i = 0; i < layout[row].length; i++) {
            if (layout[row][i] == 'Q') flag = false;
        }

        //列
        for (int i = 0; i < layout.length; i++) {
            if (layout[i][col] == 'Q') flag = false;
        }

        //左上角
        for (int i = row - 1,j = col - 1; i >= 0 && j >= 0 ; i--,j--) {
            if (layout[i][j] == 'Q')  flag = false;
        }

        //右上角
        for (int i = row-1,j = col+1;i >= 0 && j <= layout.length-1; i--,j++) {
            if (layout[i][j] == 'Q')  flag = false;
        }

        return flag;
    }

    public void init(char [][] layout,int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                layout[i][j] = '.';
            }
        }
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        int n = 4;
        char[][] layout = new char[n][n];
        nQueens.init(layout,n);
//        System.out.println(layout.length);
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.println(layout[i][j]);
//            }
//        }
        nQueens.solveNQueens(n);
        System.out.println(result);
    }


}
